package leetcode;

import base.UnionFindSet;

import java.util.HashMap;
import java.util.HashSet;

public class Leetcode128UionFindSet {

    public int find(int[] ufs, int x) {
        while (x != ufs[x])
            x = ufs[x];
        return x;
    }

    public void union(int[] ufs, int[] rank, int x, int y) {
        int xRoot = find(ufs,x);
        int yRoot = find(ufs,y);
        if (xRoot == yRoot) return;
        ufs[xRoot] = yRoot;
        rank[yRoot] += rank[xRoot];
    }

    public int longestConsecutive(int[] nums) {
        //由于nums[i] 的范围-10^9 <= nums[i] <= 10^9,所以用一个hashmap将num[i] 映射为i(0~10^5)
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        int[] ufs = new int[nums.length]; // 并查集
        int[] rank = new int[nums.length];// 记录每个集合的元素个数
        for (int i = 0; i < nums.length; i++) { // 初始化
            ufs[i] = i;
            rank[i] = 1;
        }
        for (int i = 0; i < nums.length; i++) {
            if (hashMap.containsKey(nums[i])) continue; //之前已经有过这个元素直接跳过
            hashMap.put(nums[i],i);  // 将nums[i]映射为i
            if (hashMap.containsKey(nums[i] - 1)) {
                union(ufs,rank,i,hashMap.get(nums[i] - 1));
            }
            if (hashMap.containsKey(nums[i] + 1)) {
                union(ufs,rank,i,hashMap.get(nums[i] + 1));
            }
        }
        int maxSet = 0;
        for (int i = 0; i < rank.length; i++) {
         if (maxSet < rank[i]) maxSet = rank[i];
        }
        return maxSet;
    }


}
